package chap02.Order;

/**
 * Created by root on 2017/4/26.
 */
public class OrdArray {
    private long[] a;
    private int nElems;

    public OrdArray(int max){
        a = new long[max];
        nElems = 0;
    }

    public int size(){
        return nElems;
    }

    public void display(){
        for (int j=0; j<nElems; j++) {
            System.out.print(a[j] + " ");
        }
        System.out.println();
    }

    public void insert(long value){
        int lowBound = 0;
        int upperBound = nElems - 1;
        int curIn;
        while (true) {
            curIn = (lowBound + upperBound)/2;
            if (a[curIn] == value) {
                break;
            }else if (lowBound > upperBound ) {
                break;
            }else {
                if (a[curIn] < value) {
                    lowBound = curIn + 1;
                } else {
                    upperBound = curIn -1;
                }
            }
        }
        //从current+1开始插入
        for (int j = nElems; j>lowBound; j--) {
            a[j] = a[j-1];
        }
        a[lowBound] = value;
        nElems++;
    }

    public int find(long searchKey){
        int lowBound = 0;
        int upperBound = nElems - 1;
        int curIn;
        while (true) {
            curIn = (lowBound + upperBound)/2;
            System.out.print("current " + curIn);
            System.out.println("       currentVal " + a[curIn]);
            if (a[curIn] == searchKey) {
                return curIn;
            }else if (lowBound > upperBound ) {
                return nElems;
            }else {
                if (a[curIn] < searchKey) {
                    lowBound = curIn + 1;
                } else {
                    upperBound = curIn -1;
                }
            }
        }
    }

    public boolean delete(long searchKey){
        int i = find(searchKey);
        if (i == nElems) {
            return false;
        } else {
            for (int k=i; k<nElems-1; k++) {
                a[k] = a[k+1];
            }
            nElems--;
            return true;
        }
    }

    /**
     * 简单合并
     * @param arr
     * @return
     */
    public OrdArray merge(OrdArray arr){
        int size = this.size() + arr.size();
        OrdArray allArr = new OrdArray(size);
        for (int i=0; i<arr.size(); i++) {
            allArr.insert(arr.a[i]);
        }
        for (int i=0; i<size(); i++) {
            allArr.insert(a[i]);
        }
        return allArr;
    }

    /**
     * 归并算法
     * @param arr
     * @return
     */
    public OrdArray merge2(OrdArray arr){
        int a_len = this.size();
        int b_len = arr.size();
        OrdArray allArr = new OrdArray(a_len+b_len);
        int i=0, j=0, k=0;
        while (i<a_len && j<b_len) {
            if (a[i] < arr.a[i]) {
                allArr.a[k++] = a[i++];
            } else {
                allArr.a[k++] = arr.a[j++];
            }
        }
        if (i==a_len) {
            while (j<b_len) {
                allArr.a[k++] = arr.a[j++];
            }
        } else {
            while (i<a_len) {
                allArr.a[k++] = a[i++];
            }
        }
        return allArr;
    }

    public void noDup(){
        long NULL = -1;
        for (int i=0; i<nElems; i++) {
            for (int j=i+1; j<nElems; j++) {
                if (a[i] != NULL && a[i] == a[j]) {
                    a[j] = NULL;
                }
            }
        }
        for (int i=0; i<nElems; i++) {
            if (a[i] == -1) {
                for (int k=i; k<(nElems-1); k++) {
                    a[k] = a[k+1];
                }
                i--;
                nElems--;
            }
        }
    }

}
